#include <stdio.h>
#include <stdlib.h>
#include "graph.h"

int Init(Graph *graph)
{
	graph->MaxVertex = Default_Vertex_Size;
	graph->NumVertex = graph->NumEdge = 0;
	graph->VertexList = malloc(sizeof(datatype) * graph->MaxVertex);
	if (graph->VertexList == NULL)
		return -1;
	graph->Edge = malloc(sizeof(int *) * graph->MaxVertex);
	if (graph->Edge == NULL)
		return -2;
	for (int i = 0; i < graph->MaxVertex; i++)
	{
		graph->Edge[i] = malloc(sizeof(int) * graph->MaxVertex);
		if (graph->Edge[i] == NULL)
			return -3;
	}
	for (int i = 0; i < graph->MaxVertex; i++)
		for (int j = 0; j < graph->MaxVertex; j++)
			graph->Edge[i][j] = 0;
	return 0;
}

void Show(Graph *graph)
{
	printf("  ");
	for (int i = 0; i < graph->NumVertex; i++)
		printf("%c ", graph->VertexList[i]);
	printf("\n");
	for (int i = 0; i < graph->NumVertex; i++)
	{
		printf("%c ", graph->VertexList[i]);
		for (int j = 0; j < graph->NumVertex; j++)
			printf("%d ", graph->Edge[i][j]);
		printf("\n");
	}
}

int InsertVertex(Graph *graph, datatype vertex)
{
	if (graph->NumVertex == graph->MaxVertex)
		return -1;
	graph->VertexList[graph->NumVertex++] = vertex;
	return 0;
}

int GetVertexPosition(Graph *graph, datatype vertex)
{
	for (int i = 0; i < graph->NumVertex; i++)
	{
		if (graph->VertexList[i] == vertex)
			return i;
	}

	return -1;
}

int InsertEdge(Graph *graph, datatype vertex1, datatype vertex2)
{
	int p1 = GetVertexPosition(graph, vertex1);
	int p2 = GetVertexPosition(graph, vertex2);
	if (p1 == -1 || p2 == -1)
		return -1;
	else if (p1 == p2)
		return -2;
	if (graph->Edge[p1][p2] != 0)
		return -3;
	graph->Edge[p1][p2] = graph->Edge[p2][p1] = 1;
	++graph->NumEdge;

	return 0;
}

int RemoveVertex1(Graph *graph, datatype vertex)
{
	int numedge = 0;

	int pos = GetVertexPosition(graph, vertex);
	if (pos == -1)
		return -1;
	//顶点列表中的删除顶点后的顶点前移
	for (int i = pos; i < graph->NumVertex - 1; ++i)
		graph->VertexList[i] = graph->VertexList[i + 1];
	//统计删除顶点连接的边数
	for (int i = 0; i < graph->NumVertex; ++i)
		numedge += graph->Edge[pos][i];
	//行上移
	for (int i = pos; i < graph->NumVertex - 1; ++i)
		for (int j = 0; j < graph->NumVertex; ++j)
			graph->Edge[i][j] = graph->Edge[i + 1][j];
	//列上移
	for (int i = pos; i < graph->NumVertex - 1; ++i)
		for (int j = 0; j < graph->NumVertex; ++j)
			graph->Edge[j][i] = graph->Edge[j][i + 1];
	--graph->NumVertex;
	graph->NumEdge -= numedge;
	return 0;
}

int RemoveVertex2(Graph *graph, datatype vertex)
{
	int numedge = 0;

	int pos = GetVertexPosition(graph, vertex);
	if (pos == -1)
		return -1;
	for (int i = 0; i < graph->NumVertex; ++i)
		numedge += graph->Edge[pos][i];
	//修改顶点列表
	graph->VertexList[pos] = graph->VertexList[graph->NumVertex - 1];
	//行覆盖
	for (int i = 0; i < graph->NumVertex; i++)
		graph->Edge[pos][i] = graph->Edge[graph->NumVertex - 1][i];
	//列覆盖
	for (int i = 0; i < graph->NumVertex; i++)
		graph->Edge[i][pos] = graph->Edge[i][graph->NumVertex - 1];

	--graph->NumVertex;
	graph->NumEdge -= numedge;

	return 0;
}

int RemoveEdge(Graph *graph, datatype vertex1, datatype vertex2)
{
	int p1 = GetVertexPosition(graph, vertex1);
	int p2 = GetVertexPosition(graph, vertex2);
	if (p1 == -1 || p2 == -1)
		return -1;
	if (graph->Edge[p1][p2] == 0) //本来就没有边
		return -2;
	graph->Edge[p1][p2] = graph->Edge[p2][p1] = 0;
	--graph->NumEdge;
	return 0;
}

int GetFirstNeighbor(Graph *graph, datatype vertex)
{
	int pos = GetVertexPosition(graph, vertex);
	if (pos == -1)
		return -1;
	for (int i = 0; i < graph->NumVertex; ++i)
	{
		if (graph->Edge[pos][i] == 1)
			return i;
	}
	return -2;
}

int GetNextNeighbor(Graph *graph, datatype vertex1, datatype vertex2)
{
	int p1 = GetVertexPosition(graph, vertex1);
	int p2 = GetVertexPosition(graph, vertex2);
	if (p1 == -1 || p2 == -1)
		return -1;
	if (graph->Edge[p1][p2] == 0) // p2结点本身就不是p1的邻接顶点
		return -1;
	for (int i = p2 + 1; i < graph->NumVertex; i++)
	{
		if (graph->Edge[p1][i] == 1)
			return i;
	}
	return -1;
}

void DestoryGraph(Graph *graph)
{
	free(graph->VertexList);
	graph->VertexList = NULL;
	for (int i = 0; i < graph->MaxVertex; i++)
		free(graph->Edge[i]);
	free(graph->Edge);
	graph->Edge = NULL;
	graph->MaxVertex = graph->NumVertex = graph->NumEdge = 0;
}